package com.example.demo.leetcode;

import java.util.Arrays;

// 贪心算法 不能解决所有问题
@Deprecated
public class Leetcode322 {

    /**
     * @param coins  从大到小 降序排列
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        // 剩余还需要凑多少钱
        int remainder = amount;
        int count = 0;
        for (int i = 0; i < coins.length; i++) {
            while (remainder > coins[i]) {
                remainder -= coins[i];
                count++;
            }
            // 查漏补缺 [5,2,1] 凑够15
            if (remainder == coins[i]) {
                remainder = 0;
                count++;
                break;
            }
        }
        if (remainder > 0) {
            return -1;
        } else {
            return count;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Leetcode322().coinChange(new int[]{5, 2, 1}, 11));
    }
}
